package com.acyouzi.leetcode.backtrack;

import java.util.Arrays;

/**
 * 17/9/26 20:57
 *
 * @author sunxu
 */
public class MatchsticksSquare {
  public boolean makesquare(int[] nums) {
    if (nums == null || nums.length < 4) return false;
    int sum = Arrays.stream(nums).reduce((x,y) -> x + y).getAsInt();
    if (sum % 4 != 0) return false;
    sum /= 4;
    boolean[] flag = new boolean[nums.length];
    int[] res = new int[4];
    Arrays.sort(nums);
    return helper(res,nums,0,sum);
  }

  private boolean helper(int[] res, int[] nums, int pos, int sum) {
    if (pos >= nums.length && res[0] == sum && res[1] == sum && res[2] == sum) return true;
    if (pos >= nums.length) return false;
    for (int i = 1; i < 4; i++) {
      if (res[i] + nums[pos] > sum) continue;
      res[i] += nums[pos];
      if (helper(res,nums,pos+1,sum)) return true;
      res[i] -= nums[pos];
    }
    return false;
  }
}
